#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e6+5,mod = 9989244353;
int T;
namespace sub1{
	const int N = 100;
	int n,m,U[N],V[N],a[N][2],dis[N][N],ans1,ans2;
	bool vis[N][N];
	inline void work()
	{
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=n;j++)
				if(i!=j) dis[i][j] = 2e15;
				else dis[i][j] = 0;
		for(int i = 1;i<m;i++) dis[a[i][0]][a[i][1]] = dis[a[i][1]][a[i][0]] = 1;
		for(int k = 1;k<=n;k++)
			for(int i = 1;i<=n;i++)
				for(int j = 1;j<=n;j++)
					dis[i][j] = min(dis[i][j],dis[i][k]+dis[j][k]);
		int now = 0;
		for(int i = 1;i<=m;i++) now-=dis[U[i]][V[i]];
	//	if(now<=-2e15) return;
		if(now>ans1) ans1 = now,ans2 = 1;
		else if(now==ans1) ans2++;
	}
	void dfs(int x,int lasu,int lasv)
	{
		if(x==m) return work();
		for(int i = max(lasu,1ll);i<=n;i++)
			for(int j = i;j<=n;j++)
				if(i>lasu||j>lasv)
				{
					a[x][0] = i,a[x][1] = j;
					dfs(x+1,i,j);
				}
	}
	inline void solve()
	{
		cin>>n>>m;
		for(int i = 1;i<=m;i++)
			cin>>U[i]>>V[i];
		ans1 = -2e18,ans2 = 0;
		dfs(1,0,0);
		cout<<ans1<<' '<<ans2<<'\n';
	}
	inline void main(){while(T--)solve();}
}
namespace sub2{
	int n,fac[N],inv[N];
	inline int qpow(int x,int y)
	{
		int res = 1;
		while(y)
		{
			if(y&1) res = res*x%mod;
			y>>=1;
			x = x*x%mod; 
		}
		return res;
	}
	inline int c(int x,int y)
	{
		if(x<0||y<0||x<y) return 0;
		return fac[x]*inv[y]%mod*inv[x-y]%mod;
	}
	inline void solve()
	{
		cin>>n>>n;
		for(int i = 1,x;i<=n;i++) cin>>x>>x;
		cout<<-2*(n-1)<<' '<<0<<'\n';
	}
	inline void main()
	{
		fac[0] = inv[0] = 1;
		int lim = 1e4;
		for(int i = 1;i<=lim;i++)
			fac[i] = fac[i-1]*i%mod;
		inv[lim] = qpow(fac[lim],mod-2);
		for(int i = lim-1;i;i--) inv[i] = inv[i+1]*(i+1)%mod;
//		cout<<fac[10]<<' '<<inv[2]<<":"<<c(4,2)<<'\n';
		while(T--)solve();
	}
}
signed main()
{
	freopen("oi.in","r",stdin);
	freopen("oi.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int subid;cin>>subid>>T;
	if(subid<=2) sub1::main();
	else sub2::main();
	return 0;
}
/*
-4 3
-6 12
-8 55
-10 273
-12 1428
-14 7752
3 12 55 273 1428
*/
